\documentclass{fsttcs}

%\usepackage{times}
%\usepackage[small,compact]{titlesec}
%\usepackage[small,it]{caption}

%\usepackage{fullpage}
%
%%\usepackage{times}
%
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{epsfig}
\usepackage{pstricks, pst-node}
\usepackage{algorithm}
\usepackage{algorithmic}
%\usepackage{amsthm}


\newcommand{\squishlist}{
 \begin{list}{$\bullet$}
  { \setlength{\itemsep}{0pt}
     \setlength{\parsep}{3pt}
     \setlength{\topsep}{3pt}
     \setlength{\partopsep}{0pt}
     \setlength{\leftmargin}{1.5em}
     \setlength{\labelwidth}{1em}
     \setlength{\labelsep}{0.5em} } }

\newcommand{\squishlisttwo}{
 \begin{list}{$\bullet$}
  { \setlength{\itemsep}{0pt}
     \setlength{\parsep}{0pt}
    \setlength{\topsep}{0pt}
    \setlength{\partopsep}{0pt}
    \setlength{\leftmargin}{2em}
    \setlength{\labelwidth}{1.5em}
    \setlength{\labelsep}{0.5em} } }

\newcommand{\squishend}{
  \end{list}  }


%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{lemma}[theorem]{Lemma}
%%\newtheorem{theorem}{Theorem}
%%\newtheorem{lem}{Lemma}
%%\newtheorem{proposition}{Proposition}
%%\newtheorem{claim}{Claim}
%%\newtheorem{fact}{Fact}
%%\newtheorem{corollary}{Corollary}
%\newtheorem{definition}{Definition}
%%\newenvironment{pf}{{\bf Proof:}}{\hfill\rule{1.5mm}{3mm}\vspace{0.1in}}

\newtheorem{invariant}{Invariant}

%\newcommand{\pr}{{\mathbf{Pr}}}
%\newcommand{\E}{{\mathbf E}}
%
%\newcommand{\pr}{{\mathrm Pr}}
%
%\newcommand{\sbinom}[2]{\left( \stackrel{{#1}}{_{#2}} \right)}
%
%\newcommand{\nchoosetwo}{\sbinom{n}{2}}
%
\newcommand{\integer}{{\mathbb Z}}
\newcommand{\real}{{\mathbb R}}
%
\newcommand{\pname}[1]{{\sc #1}}
%
\newcommand{\comment}[1]{}
%
\newcommand{\figframe}[3]{
\begin{figure}
\begin{center}
\fbox{
\begin{minipage}[t]{#1}
#2
\end{minipage}
}
\end{center}
#3
\end{figure}
}
%
%\long\def\symbolfootnotetext[#1]#2{\begingroup%
%\def\thefootnote{\fnsymbol{footnote}}\footnotetext[#1]{#2}\endgroup}
%
%\pagestyle{plain}
%\usepackage{fullpage}
%\newcommand{\delete}[1]{}
\def\polylog{\operatorname{polylog}}
\def\cf{{\em cf.}}

\begin{document}

\title{5.24-Approximation Semi-Streaming Algorithm for Weighted Maximum Matching}

% These are required for headers and for copyright on title page
\runningtitle{5.24-Approximation Matching on Semi-Stream}
\runningauthors{Das Sarma, Lipton, Nanongkai}

% Multiple authors, sharing an affiliation, use  \affiliation{...}

\author{Atish Das Sarma,
  Richard J. Lipton, Danupon Nanongkai}

\affiliation{
  Georgia Institute of Technology\\
  USA\\
  \email{\{atish,rjl,danupon\}@cc.gatech.edu}
}

\begin{abstract}
We consider the maximum weight matching problem in the one-pass
semi-streaming setting. In this setting, only $O(n\polylog{n})$ bits
of memory is allowed where $n$ is the number of vertices. We improve
the best known approximation ratio from 5.585 by Zelke [STACS'08] to
5.24 by presenting a new algorithm {\sc GlobalShadowMatching}.
%
%We show that a modification of Zelke's algorithm [STACS'08] admit a
%5.45 approximation ratio
%
%for a single machine have been developed, improving the
%approximation guarantee from 6 to 5.58 over papers~\cite{FKMSZ05,
%McGregor05, Zelke08}. We show that a slight modification of Zelke's
%algorithm~\cite{Zelke08} improves the approximation guarantee from
%5.58 to 4.62.
\end{abstract}

\input{intro}
\input{algo}
\input{analysis_overview}
\input{simplification}
\input{charging_scheme}
\input{invariant_proofs}
\input{conclusion}



% \let\oldthebibliography=\thebibliography
%  \let\endoldthebibliography=\endthebibliography
%  \renewenvironment{thebibliography}[1]{%
%    \begin{oldthebibliography}{#1}%
%      \setlength{\parskip}{0ex}%
%      \setlength{\itemsep}{0ex}%
%  }%
%  {%
%    \end{oldthebibliography}%
%  }
{\small
\bibliographystyle{plain}
%\bibliographystyle{alpha}
\bibliography{matching}
}

\newpage
\appendix
\input{appendix}


\end{document}
